{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!/usr/bin/env python3\n",
    "\"\"\" 找零钱问题\n",
    "# 对于现实生活中的找零问题，假设有数目不限，面值为2,5,10的硬币, 求出找零方案。\n",
    "# 发现这个问题跟 鸡兔同笼，背包问题\n",
    "# 对于此类问题，贪心算法可以找到近似最优解；\n",
    "# 动态规划可以找到最优解；其中也可以根据具体情况做一些优化。\n",
    "# \n",
    "# moneyValues = [2,5,10]\n",
    "# moneyCount = [i, j, k]  #示例 [30,40,50]\n",
    "# price = N #示例 95\n",
    "\n",
    "# Testtcases：(从面值大的币种查找的用例)\n",
    ">>> change([2,5,10],[30,40,50],95)\n",
    "95 可找零为 9 张10元，1 张5元，0 张2元\n",
    "\n",
    ">>> change([2,5,10],[30,40,50],94)\n",
    "94 可找零为 9 张10元，0 张5元，2 张2元\n",
    "\n",
    ">>> change([2,5,10],[30,40,50],90)\n",
    "90 可找零为 9 张10元，0 张5元，0 张2元\n",
    "\n",
    ">>> change([2,5,10],[30,40,50],109)\n",
    "109 可找零为 10 张10元，1 张5元，2 张2元\n",
    "\n",
    "# 判断币种组合\n",
    ">>> change([2,5,10],[30,40,50],93)\n",
    "93 不能找零\n",
    "\n",
    ">>> change([2,5,10],[30,40,50],91)\n",
    "91 不能找零\n",
    "\n",
    "# 判断数量限制\n",
    ">>> change([2,5,10],[5,40,5],90)\n",
    "90 可找零为 5 张10元，8 张5元，0 张2元\n",
    "\n",
    ">>> change([2,5,10],[30,0,50],95)\n",
    "95 不能找零\n",
    "\n",
    ">>> change([2,5,10],[30,40,1],94)\n",
    "94 可找零为 1 张10元，16 张5元，2 张2元\n",
    " \"\"\"\n",
    "\n",
    "def change(moneyValues, moneyCount, priceN):\n",
    "    moneyCounts = dict(zip(moneyValues, moneyCount))\n",
    "    if not assert_kinds_enough(moneyValues, priceN):\n",
    "        return display(None, priceN)\n",
    "\n",
    "    rst = get_DP_set_from_max(moneyCounts, priceN)\n",
    "    # rst = get_DP_set_from_min(moneyCounts, priceN)\n",
    "    # rst = get_greedy_set(moneyValues, priceN)\n",
    "    return display(rst, priceN)\n",
    "\n",
    "def get_DP_set_from_max(moneyCounts, priceN):\n",
    "    # 规划 i,j,k 的“最优”组合，算法复杂度主要在此\n",
    "    # 动态规划\n",
    "    \n",
    "    # 尽量使用大额面值，这样张数最少，且少了一层循环\n",
    "    # 时间复杂度为 面值种类数M，空间复杂度为O(1),结果的 rst 用的一个有限 dict\n",
    "    moneyCounts = dict(sorted(moneyCounts.items(), key=lambda x:x[0], reverse=True))\n",
    "    rst = {value:0 for value, count in moneyCounts.items()}\n",
    "    if sum(value * count for value, count in moneyCounts.items()) < priceN:\n",
    "        return None\n",
    "    for value, count in moneyCounts.items():\n",
    "        if priceN <= 0:\n",
    "            break\n",
    "        tmpCount = priceN // value\n",
    "        if count > 0 or count >= tmpCount:\n",
    "            if count <= tmpCount:\n",
    "                rst[value] += count\n",
    "            else:\n",
    "                rst[value] += tmpCount\n",
    "            priceN -= rst[value] * value\n",
    "        else:\n",
    "            continue\n",
    "    if priceN > 0:\n",
    "        return None\n",
    "    else:\n",
    "        return rst\n",
    "\n",
    "def get_DP_set_from_min(moneyCounts, priceN):\n",
    "    # 规划 i,j,k 的“最优”组合，算法复杂度主要在此\n",
    "    # 动态规划\n",
    "    \n",
    "    # 尽量使用小额面值，这样张数最多，在张数限制下确定是否有解\n",
    "    # 时间复杂度 O(MN),M为面值种类数，N为给定的找零的钱数；空间复杂度为O(1),结果的 rst 用的一个有限 dict\n",
    "    moneyCounts = sorted(moneyCounts.items(), key=lambda x:x[0], reverse=False)\n",
    "    rst = {moneyValue:0 for moneyValue, count in moneyCounts}\n",
    "    if sum(moneyValue * count for moneyValue, count in moneyCounts) < priceN:\n",
    "        return None\n",
    "    for i in range(0,len(moneyCounts)):\n",
    "        iCount = 0\n",
    "        if moneyCounts[i][1] <= 0:\n",
    "            continue\n",
    "        for j in range(0, moneyCounts[i][1]+1):\n",
    "            if i > (len(moneyCounts)-2):\n",
    "                break\n",
    "            if (priceN - moneyCounts[i][0]*j) % moneyCounts[i+1][0] == 0:\n",
    "                iCount = j\n",
    "            if iCount*moneyCounts[i][0] >= priceN:\n",
    "                break\n",
    "        if iCount != 0:\n",
    "            rst[moneyCounts[i][0]] += iCount\n",
    "            priceN -= iCount * moneyCounts[i][0] \n",
    "        elif  moneyCounts[i][1] == 0:\n",
    "            continue\n",
    "        else:\n",
    "            rst[moneyCounts[i][0]] += priceN // moneyCounts[i][0]\n",
    "            priceN -= rst[moneyCounts[i][0]] * moneyCounts[i][0]\n",
    "        if priceN <= 0:\n",
    "            break\n",
    "    if priceN > 0:\n",
    "        return None  \n",
    "    return rst\n",
    "\n",
    "def get_greedy_set(moneyValues, priceN):\n",
    "    # 规划 i,j,k 的“最优”组合：贪心算法\n",
    "    # 时间复杂度 O(MN),M为面值种类数，N为给定的找零的钱数；空间复杂度 O(1),至多用到2个确定大小的 dict\n",
    "    \n",
    "    # 尽量使用大额面值，不考虑币种数量限制\n",
    "    moneyValues = sorted(moneyValues, reverse=True)\n",
    "\n",
    "    rst = {moneyValue:0 for moneyValue in moneyValues}\n",
    "    for moneyValue in moneyValues:\n",
    "        while priceN >= moneyValue and priceN > 0:\n",
    "            priceN -= moneyValue\n",
    "            rst[moneyValue] += 1\n",
    "    return rst\n",
    "\n",
    "def assert_kinds_enough(moneyValues, price):\n",
    "    # 面值中不包含1， 所以定有一部分 N 不能够组合，如1, 3, 等\n",
    "    if price % 5 == 0:\n",
    "        return True\n",
    "    elif price % 2 == 0:\n",
    "        return True\n",
    "    elif (price % 5 != 0) and ((price % 5) % 2 == 0):\n",
    "        return True\n",
    "    else:\n",
    "        return None\n",
    "\n",
    "def display(rst, price):\n",
    "    if rst:\n",
    "        print(f\"{price} 可找零为 {rst[10]} 张10元，{rst[5]} 张5元，{rst[2]} 张2元\")\n",
    "    else:\n",
    "        print(f\"{price} 不能找零\")\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
